package LeetCode.month03.day65;

/**
 * @author 16778
 * @date 2025/9/29 11:03
 * @description
 */
public class No395 {

    public int longestSubstring(String s, int k) {
        int n = s.length();
        return dfs(s,0,n-1,k);
    }

    private int dfs(String s, int l, int r, int k) {
        int[] cnt = new int[26];
        for (int i = l; i <= r; i++) {
            int index = s.charAt(i)-'a';
            cnt[index]++;
        }
        char split = 0;
        for (int i = 0; i < 26; i++) {
            if(cnt[i]>0&&cnt[i]<k){
                split = (char)('a'+i);
                break;
            }
        }
        if(split == 0 )
            return r-l+1;

        int i = l;
        int res = 0;
        while(i<=r){
            while(i<=r&&s.charAt(i)==split){
                i++;
            }
            if(i>r){
                break;
            }
            int start = i;
            while(i<=r&&s.charAt(i)!=split){
                i++;
            }
            res = Math.max(dfs(s,start,i-1,k),res);
        }
        return res;
    }

    public int longestSubstring2(String s, int k) {
        int n = s.length();
        int res = 0;
        for (int i = 1; i <= 26; i++) {
            int[] cnt = new int[26];
            int l= 0;
            int index = 0;
            int less = 0;
            int tol = 0;
            while(index<n){
                cnt[s.charAt(index)-'a']++;
                if(cnt[s.charAt(index)-'a']==1){
                    tol++;
                    less++;
                }
                if(cnt[s.charAt(index)-'a']==k){
                    less--;
                }
                while(tol>i){
                    cnt[s.charAt(l)-'a']--;
                    if(cnt[s.charAt(l)-'a']==k-1){
                        less++;
                    }
                    if(cnt[s.charAt(l)-'a']==0){
                        tol--;
                        less--;
                    }
                    l++;
                }
                if(less==0){
                    res = Math.max(res,index-l+1);
                }
                index++;
            }
        }
        return res;
    }
}
